package leetcode.primary;


public class T239 {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums.length==1 || k==1){
            return nums;
        }
        MonotoneQueue queue = new MonotoneQueue(nums.length);
        int[] ans = new int[nums.length+1-k];
        int j = 0;
        for (int i = 0;i < k;i++){
            queue.InQueue(nums[i]);
        }
        int tail = k-1;
        while (tail< nums.length){
            ans[j++] = queue.getHead();
            queue.DeQueue(nums[tail-k+1]);
            if(++tail<nums.length){
                queue.InQueue(nums[tail]);
            }

        }
        return ans;

    }

    public static void main(String[] args) {
        T239 t239 = new T239();
        int[] maxs = t239.maxSlidingWindow(new int[]{9,11}, 2);
        for (int max : maxs) {
            System.out.print(max+" ");
        }
    }
}

//单调队列
class MonotoneQueue{
    int head,tail;
    int[] nums ;

    public MonotoneQueue(int length){
        nums = new int[length];
        head = 0;
        tail = 0;
    }

    public int getHead(){
        return nums[head];
    }

    //入队
    public void InQueue(int element){
        if (tail>=nums.length){
            return;
        }
        int i = tail-1;
        if (i>=0){
            while (i>=head && nums[i]< element){
                i--;
            }
        }
        tail = i+1;
        nums[tail++] = element;
    }

    //出队
    public void DeQueue(int element){
        if (head==tail){
            return;
        }
        if (element>=nums[head]){
            head++;
        }
    }
}